package com.itheima.algorithm.datastructure;

/**
 * 合并两个有序链表
 * @Author: zhangshao
 * @Since: 2024/4/30 15:06
 */
public class Leetcode21 {

	/**
	 *
	 * @param p1
	 * @param p2
	 * @return
	 */
	 public static ListNode mergeTwoList(ListNode p1,ListNode p2){
		ListNode s = new ListNode(-1,null);
		ListNode p =s;
		while (p1!=null && p2!=null){
			// p1节点值更小
			if(p1.value < p2.value){
				p.next = p1;
				p1 = p1.next;
				p = p.next;
			}else{
				p.next = p2;
				p2 = p2.next;
				p = p.next;
			}
		}
		if(p1!=null){
			p.next = p1;
		}
		if(p2!=null){
			p.next = p2;
		}
		return s.next;
	 }

	/**
	 * 递归返回
	 * @param p1
	 * @param p2
	 * @return
	 */
	 public static ListNode mergeTwoListByRecursion(ListNode p1,ListNode p2){
	 	if(p2 == null){
	 		return p1;
		}
	 	if(p1==null){
	 		return p2;
		}
	 	if(p1.value<p2.value){
	 		p1.next = mergeTwoListByRecursion(p1.next,p2);
	 		return p1;
		}else{
			p2.next = mergeTwoListByRecursion(p1,p2.next);
			return p2;
		}
	 }



	public static void main(String[] args) {
		ListNode p1 =ListNode.of(1,3,8,9);
		ListNode p2 =ListNode.of(2,4);

		System.out.println(mergeTwoListByRecursion(p1,p2));

	}

}
